Data switches, such as Ethernet switches, are well known which transfer data packets between ingress/egress ports connected by a switching fabric controlled by a control unit. Two or more of the ports of the switch are connected (either directly or via other devices or networks) to devices having MAC (medium access control) addresses. Each of the data packets contains a destination address specifying the MAC address of the device to which the data packet is directed and an origin address specifying the MAC address of the device where the packet originated.
When the switch is first turned on, it typically does not “know” the MAC addresses of the devices connected to it, and which ports those devices are connected to. Typically, the device learns this information automatically using the data packets it receives, by extracting the origin addresses from the data packets and noting which port the data packet arrived at. The association between these two pieces of information is stored in a MAC address table (“MA table”). A variety of algorithms are known for constructing the table. When a data packet is received containing a destination address, the switch can look up the address in the MA table, find the associated port, and transmit the data packet to that port, for onward transmission to the device having that MAC address.
A significant problem, however, is that if the switch is transmitting data among a very large number of devices, the size of the MA table must become very great. This is especially true because many of the algorithms for generating MA tables are inefficient in terms of the amount of writable memory required in relation to the amount of data which it actually has to store.